/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) 
{
    //1.拷贝节点链接在源节点后面    
     struct Node*cur=head;
     while(cur)
     {
            struct Node *next = cur->next;
            struct Node*copy = (struct Node*) malloc(sizeof(struct Node));
             copy->val=cur->val;
              
             cur->next=copy;
             copy->next=next;
              
             cur =next;
     }

     //2.置 random

     cur =head;
     while(cur)
     {
         struct Node* copy =cur->next;
       if(cur->random ==NULL)
       {
           copy->random =NULL;
       }    
       else
       {
           copy->random =cur->random->next; // 666
       }
       cur =cur->next->next;
     }

    //3. 解下来链接在一起
    cur =head;
    
    struct Node* copyhead = NULL, *copytail =NULL;
    while(cur)
    {
        struct Node* copy =cur->next;
        struct Node*next=copy->next;

        cur->next =next;    
       //尾插
       if(copytail == NULL)
       {
           copyhead =copytail =copy;
       }
       else
       {
          copytail->next =copy;
          copytail =copytail->next;
       }
       cur =next;
    }

    return copyhead;

}